public class heap {
    public static int MAXN = 10001;
    public static int[] arr = new int[MAXN];
    public static int n;

    public static void heapSort() {
        // 插入堆中,维护成大根堆
        for (int i = 0; i < n; i++) {
            insertHeap(i);
        }
        // 按从小到大排序
        int size = n;
        while (size > 1) {
            swap(0,--size);
            heapify(0,size);
        }
    }

    //     0
    //   1   2
    //  3 4 5 6

    private static void heapify(int i, int size) {
        int l = 2 * i + 1; // 左边的位置
        while (l < size) {
            // 找到下面两个最大的,进行比较
            int best = l + 1 < size && arr[l] <arr[l + 1] ? l + 1:l;
            if (arr[best] > arr[i]) {
                swap(best,i);
                i = best;
                l = best * 2 + 1;
            } else {
                break;
            }
        }
    }

    private static void swap(int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }

    //     0
    //   1   2
    // 3
    private static void insertHeap(int i) {
        while (arr[(i - 1) / 2] < arr[i]) {
            swap((i - 1) / 2,i);
            i =  (i - 1) / 2;
        }
    }

    public static void main(String[] args) {
        arr = new int[]{3,545,65,3,4312,2};
        n = 6;
        heapSort();
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");

        }
    }
}
